package gold.gold02;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 简单
 * 树, 创建树，递归
 * 这题挺好的
 * 先进行一次排序, 再用有序数列建立二叉搜索树, 递归一下。(输入本来就是有序的。)
 * 28, 不过大家时间都是0, 方法一样, 意义不大。
 *
 */
public class S0402最小高度树 {
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums.length == 0) return null;
        // 这里的这些操作要熟练。直接for也可以
        List<Integer> numsList = Arrays.stream(nums).boxed().collect(Collectors.toList());
        Collections.sort(numsList);

        return getBSTFromSorted(numsList);
    }

    private TreeNode getBSTFromSorted(List<Integer> inputList){
        int totalLen = inputList.size();
        if(totalLen == 0) return null;
        if(totalLen == 1) return new TreeNode(inputList.get(0));
        int midPosi = inputList.size()/2;
        TreeNode node0 = new TreeNode(inputList.get(midPosi));
        // List接口的subList方法, 第二个参数取不到
        node0.left = getBSTFromSorted(inputList.subList(0, midPosi));

        node0.right = getBSTFromSorted(inputList.subList(midPosi+1, inputList.size()));
        return node0;
    }

    public static void printTreeNode(TreeNode inputNode){
        if(inputNode == null) return;
        System.out.println("结果节点: " + inputNode.val);
        printTreeNode(inputNode.left);
        printTreeNode(inputNode.right);
    }

    public static void main(String[] args) {
        int[] input = {1, 2, 3, 4, 2, 3, 6, 1};
        TreeNode result = new S0402最小高度树().sortedArrayToBST(input);
        printTreeNode(result);
    }
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
